/**
 * @param {number[]} nums
 * @return {number}
 */
 var minimumDifference = function(nums) {
  const n = nums.length, m = n/2
  const sum = nums.reduce((pre,cur) => pre+cur, 0)
  nums.sort((a,b) => a-b)
  let half = 0, dis = Infinity
  const dfs = (now, idx, cnt) => {
    if(cnt === m){
      if(Math.abs(now - sum/2) < dis){
        half = now
        dis = Math.abs(now - sum/2)
      }
      return
    }
    for(let i = idx; i<n; i++){
        if(n - i >= m - cnt){
          dfs(now+nums[i], i+1, cnt+1)
        }
    }
  }
  dfs(0, 0, 0)
  return Math.abs(2 * half-sum);
};